/**
 * 剑指 Offer 22. 链表中倒数第k个节点
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，
 * 本题从1开始计数，即链表的尾节点是倒数第1个节点。
 * 例如，一个链表有 6 个节点，从头节点开始，
 * 它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
 * 示例：
 * 给定一个链表: 1->2->3->4->5, 和 k = 2.
 *
 * 返回链表 4->5.
 *
 */

public class leecode22 {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
//        ListNode listNode6 = new ListNode(6);
//        ListNode listNode7 = new ListNode(7);

        linked linked = new linked();
        linked.add(listNode1);
        linked.add(listNode2);
        linked.add(listNode3);
        linked.add(listNode4);
        linked.add(listNode5);
//        linked.add(listNode6);

        Solution solution = new Solution();
        ListNode s = solution.getKthFromEnd(listNode1, 2);
//        System.out.println(s.val);
    }

}

//      Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

}

class linked {
    private ListNode head = new ListNode(0);
    public ListNode getHead() {
        return head;
    }
    public void add(ListNode listNode){
        ListNode temp = head;
        while(temp != null){
            if (temp.next == null){
                break;
            }
            temp = temp.next;
        }
        temp.next = listNode;
    }
}

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int n = 0;
        ListNode node = null;
        for (node = head; node != null; node = node.next) {
            n++;
        }
//        System.out.println(n);
        for (node = head; n > k; n--) {
            node = node.next;
//            System.out.println(node.val);
        }
        for (int i = 0; i < n; i++) {
            System.out.println(node.val);
            node = node.next;
        }
        return node;
    }
}

